package org.algorithm.Recursion;

import java.lang.reflect.Array;
import java.util.Arrays;

public class Fibonacci
{
    public static int fibonacci(int n)
    {
        int []cache = new int[n+1];
        Arrays.fill(cache,-1);

        cache[0]=0;
        cache[1]=1;

        return function2(n,cache);

//        return function(n);
    }

    /**
     * 斐波拉契初始版本
     * @param n
     * @return
     */
    public static int function(int n)
    {
        if (n==0)
        {
            return 0;
        }

        if (n==1)
        {
            return 1;
        }

        int x = function(n-1);

        int y = function(n-2);

        return x+y;
    }


    /**
     * 优化：记忆法
     * @param n
     * @param cache
     * @return
     */
    public static int function2(int n ,int []cache)
    {

        if (cache[n]!=-1)
        {
            return cache[n];
        }

        int x= function2(n-1,cache);
        int y= function2(n-2,cache);

        cache[n]=x+y;
        return cache[n];
    }

    public static void main(String[] args) {
        int fibonacci = fibonacci(500);

        System.out.println(fibonacci);
    }
}
